#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <ctype.h>
#include <string.h>

#define MAXPOP 500
#define MAXDIM 500
#define MAXREP 10
#define NUMMAC 20
#define NUMJOB 500
#define MAXWEIGHT 0.9
#define MINWEIGHT 0.4
#define MAXGEN 1000
#define xmax 4.0
#define xmin 0.0
#define vmax 4.0
#define vmin -4.0
#define alpha 10.0
#define lamda 0.00
#define beta 2.0
#define NT 2
#define INFINITY 100000000000.0

typedef float chromosome[MAXDIM];
typedef int chromosome1[MAXDIM];
typedef struct ind{
      chromosome dchrom;
      chromosome vchrom;
      chromosome1 sequence;
      float fitness;
      }individual;

/* Function Prototyping */
float frand();
int vnd1();
int vnd2();
int vnd3();
int repair(individual *child);
int sortarpd();
int sortcpu();
int sortcpu_ebru();
int edd();
int sortedd();
int arpdstd();
int cpustd();
int cpustd_ebru();
int interchange(individual *neighbor,individual *particle,int u,int v);
int insert(individual *neighbor,individual *particle,int u,int v);
int applylocalsearch();
int applylocalsearch1();
int mutation();
int display();
float rndf(float low,float up);
int evaluate();
float urand(float low, float upper);
float readdata();
int randlist(int n,int list[]);
float randlistf(int n,float list[]);
long int rnd(long int low,long int up);
int initialize();
/*initpop();*/
int initpop(individual *oldpop);
float cfitness_cmax(int chrom[],int lbits);
float cfitness_tmax(int chrom[],int lbits);
int getsequence(individual *child);
void initreport();
individual tourselect(int k);
int updatevelocity();
int updateposition();
int evaluatelocalbest();
int evaluateglobalbest();
individual holdbest();
individual bsofar(individual *ptr);
int writebestsofar();

int rankoldpop(int ccpop);
int ranknewpop(int ccpop);
int rankpop(int ccpop);
int reorder(int newchrom[]);
/*Global Variables*/
long int seed,iseed;
int popsize;
int ldimension;
long int gen,cpop,counter,pcount;
long int maxgen;
float pmutation=0.05;
float plocalsearch=0.05;
float iweight;
int jcross1,jcross2,jcross3,jcross4;
float totdis;
int clength,NUMINSTANCE=160;

int cblock[MAXDIM];
int weight[MAXDIM];
int duedate[MAXDIM];
int ptime[NUMJOB][NUMMAC];
int mnum[NUMJOB][NUMMAC];
int tptime[NUMJOB];
int comptime[NUMJOB][NUMMAC];
int row[NUMJOB];

float flowtime[MAXDIM];
float lateness[MAXDIM];
float tardiness[MAXDIM];
float wtardiness[MAXDIM];
float maxlateness,maxtardiness;
int maxcomptime;
int noptr,pmcount,tnopti,tnimproved;
int nopti[125];
int nimproved[125];
int wtopt[125];
int njobs,nmach,improved;
int size;
float cmax_fitness,tmax_fitness;
  float rel_per_dev[5000];
  float trpd;
  float avg_rel_per_dev;
  float max_rel_per_dev;

  float cpu_time[5000],cpu_time_ebru[5000];
  float max_cpu_time=100;
  float tcpu_time,tcpu_time_ebru,tdif1,tdif2,tdif2_ebru,stdcpu,stdcpu_ebru,stdarpd;
  float avg_cpu_time,avg_cpu_time_ebru,tot_avg_rel_per_dev;

  char string[150],string1[150],string2[150],spname[20],pname[20],slbound[20],subound[20],scpu1[20],scpu2[20];
  int lbound[125],ubound[125],best[125];
  float ecpu;
  
individual oldpop[MAXPOP];
individual localbest[MAXPOP];
individual pop[MAXPOP];
FILE *fin,*fout,*fres1,*fopt,*fdata,*ftmax;

individual globalbest;
individual offspring,offspring1,offspring2,offspring3;

int main(){
  clock_t ticks;
  float newtime,oldtime;
  int i,j,k,ni,nr,ins;


  fout=fopen("initpop1.txt","w");
  fres1=fopen("OEBRU_BI_PSO-SPV_0.00.txt","a+");
  ticks=clock();
  pmcount=0;
  trpd=0;
  tnopti=0;
  tot_avg_rel_per_dev=0;
  tdif1=0;
  tdif2=0;
  tdif2_ebru=0;
  tcpu_time=0;
  tcpu_time_ebru=0;

   // readdata();
 fin=fopen("flmax.txt","r");
 for (ins=0;ins<NUMINSTANCE;ins++){
   fgets(string,150 ,fin);
   //printf("%s\n",string);getch();

   fgets(string1,150 ,fin);
   //fscanf(fin,"%s\t %s\n",&spname,&pname);

   //printf("%s\n",string1);getch();
   fscanf(fin,"%s\t %d\n",&slbound,&lbound[ins]);

   //printf("%d\n",lbound[ins]);getch();
   fscanf(fin,"%s\t %d\n",&subound,&ubound[ins]);

   //printf("%d\n",ubound[ins]);getch();
   fscanf(fin,"%s\t %s\t %f\n",&scpu1,&scpu2,&ecpu);

   //printf("%s\t %s\t %.2f\n",scpu1,scpu2,ecpu);getch();
   fgets(string1,150,fin);
   //printf("%s\n",string1);getch();

   fscanf(fin,"%d %d\n",&njobs,&nmach);
   //printf("%d\t %d\t",njobs,nmach);getch();


   for (j=0;j<njobs;j++){
   for (i=0;i<nmach;i++){
      fscanf(fin,"%d\t %d\t",&mnum[j][i],&ptime[j][i]);}
      fscanf(fin,"%d\t",&duedate[j]);}



  /*for (j=0;j<njobs;j++){
   for (i=0;i<nmach;i++){
        printf("%d\t %d\t",mnum[j][i],ptime[j][i]);}
        printf("%d\t",duedate[j]);} getch(); */
  ldimension=njobs;
   /*for (j=0;j<nmach;j++){
          for (i=0;i<njobs;i++){
            fprintf(fdist,"%d %s",ptime[i][j],",");}
            fprintf(fdist,"\n");}*/

 //for (j=0;j<nmach;j++){
   //for (i=0;i<njobs;i++){
     //   printf("%4d",ptime[i][j]);}}getch();



    //maxgen=(3300*log(njobs)+7500*log(nmach)-18500)/njobs;
    //printf("maxgen=%d",maxgen);getch();
    popsize=njobs*2;


    maxgen=500;


    improved=0;
    noptr=0;
    for (nr=0;nr<MAXREP;nr++){
      seed=856765+nr;
      srand(seed);
     if ((ticks=clock())==(clock_t)-1) oldtime=1;
        else oldtime=(float) ticks/CLOCKS_PER_SEC;


    initialize();
    //display();
    globalbest.fitness=8888889999999.0;
    evaluate();
   /* printf("%.2f",oldpop[0].fitness); getch();
    edd();
    printf("%.2f",oldpop[0].fitness); getch();
    //display(); */
    gen=0;
    iweight=0.9;
    do{
      clrscr();
      printf("replication       =%d\n",nr);
      printf("Generation        =%d\n",gen);
      printf("upperbound        =%d\n",ubound[ins]);
      printf("globalbest        =%.2f\n",globalbest.fitness);
      gen++;
      //iweight=iweight-urand(0.0,1.0)/4;
      iweight=0.975*iweight;
      if (iweight<0.4) iweight=0.4;
      //printf("%.2f",iweight);getch();
      //iweight=MAXWEIGHT-((MAXWEIGHT-MINWEIGHT)/maxgen)*gen;
      //if (iweight<0.1) iweight=0.1;
      updatevelocity();
      updateposition();

      evaluatelocalbest();
      evaluateglobalbest();
      //mutation();
      if ((ticks=clock())==(clock_t)-1) newtime=1;
        else newtime=(float) ticks/CLOCKS_PER_SEC;
      }while(gen<maxgen);

     /* clrscr();
     printf("bestglobal  fitness  =%.2f\n",globalbest.fitness);
      printf("\n");
      for (i=0;i<ldimension;i++){
        printf("%.2f %s",globalbest.dchrom[i],",");}
        printf("\n");
        printf("\n");
      for (i=0;i<ldimension;i++){
        printf("%.2f %s",globalbest.vchrom[i],",");}
        printf("\n");
        printf("\n");
      for (i=0;i<ldimension;i++){
        printf("%d %s",globalbest.sequence[i],",");}  */
        if ((ticks=clock())==(clock_t)-1) newtime=1;
        else newtime=(float) ticks/CLOCKS_PER_SEC;


      if (globalbest.fitness<ubound[ins])improved++;
            if (globalbest.fitness<=ubound[ins])noptr++;

     rel_per_dev[pmcount]=((globalbest.fitness-ubound[ins])*100)/ubound[ins];
     //printf("%.2f",rel_per_dev[pmcount]); getch();

     cpu_time[pmcount]=newtime-oldtime;
     cpu_time_ebru[pmcount]=ecpu;
     
     /* printf("ter test");getch();*/
      fprintf(fres1,"%s\n\n",string1);
      fprintf(fres1,"Replication Number j=%d\n",nr);
      fprintf(fres1,"Seed=%d Iteration=%d Popsize=%d ldimension=%d\n",seed,gen,popsize,ldimension);
      fprintf(fres1,"CPU in seconds for PSO =%.2f\n",newtime-oldtime);
      fprintf(fres1,"CPU in seconds for EBRU=%.2f\n",ecpu);
      fprintf(fres1,"relative percent dev =%.2f\n\n",rel_per_dev[pmcount]);
      fprintf(fres1,"lower bound          =%d\n",lbound[ins]);
      fprintf(fres1,"upper bound          =%d\n",ubound[ins]);
      fprintf(fres1,"globalbest  fitness  =%.2f\n",globalbest.fitness);
      fprintf(fres1,"\n");
      for (j=0;j<ldimension;j++){
        fprintf(fres1,"%.2f\t",globalbest.dchrom[j]);}
        fprintf(fres1,"\n");
      for (j=0;j<ldimension;j++){
        fprintf(fres1,"%.2f\t",globalbest.vchrom[j]);}
        fprintf(fres1,"\n");
      for (j=0;j<ldimension;j++){
        fprintf(fres1,"%d\t",globalbest.sequence[j]);}
        fprintf(fres1,"\n");

       pmcount++;
      }fprintf(fres1,"********************************************************************************************\n");

      if (noptr>0)nopti[ins]=1;
      tnopti+=nopti[ins];
      if (improved>0)nimproved[ins]=1;
      tnimproved+=nimproved[ins];

        //fprintf(fres1,"%.4f\t",trpd/MAXREP);
        //fprintf(fres1,"\n");
        fprintf(fres1,"Problem Number=%d Number of Bestknown Found =%d Number of Improved=%d\t",ins+1,tnopti,tnimproved);
        fprintf(fres1,"\n");
        fprintf(fres1,"********************************************************************************************\n");
      }
      sortarpd();
      sortcpu();
      cpustd();
      arpdstd();

      fprintf(fres1,"AVG_RPD=%.4f\t",avg_rel_per_dev);
      fprintf(fres1,"\n");
      fprintf(fres1,"MIN_RPD=%.4f\t",rel_per_dev[MAXREP*NUMINSTANCE-1]);
      fprintf(fres1,"\n");
      fprintf(fres1,"MAX_RPD=%.4f\t",rel_per_dev[0]);
      fprintf(fres1,"\n");
      fprintf(fres1,"STD_RPD=%.4f\t",stdarpd);
      fprintf(fres1,"\n");
      fprintf(fres1,"NO=%d\t",tnopti);
      fprintf(fres1,"\n");


      fprintf(fres1,"ACPU=%.4f\t",avg_cpu_time);
      fprintf(fres1,"\n");
      fprintf(fres1,"MINCPU=%.4f\t",cpu_time[MAXREP*NUMINSTANCE-1]);
      fprintf(fres1,"\n");
      fprintf(fres1,"MAXCPU=%.4f\t",cpu_time[0]);
      fprintf(fres1,"\n");
      fprintf(fres1,"STDCPU=%.4f\t",stdcpu);
      fprintf(fres1,"\n");

      sortcpu_ebru();
      cpustd_ebru();
      fprintf(fres1,"ACPU_EBRU=%.4f\t",avg_cpu_time_ebru);
      fprintf(fres1,"\n");
      fprintf(fres1,"MINCPU_EBRU=%.4f\t",cpu_time_ebru[MAXREP*NUMINSTANCE-1]);
      fprintf(fres1,"\n");
      fprintf(fres1,"MAXCPU_EBRU=%.4f\t",cpu_time_ebru[0]);
      fprintf(fres1,"\n");
      fprintf(fres1,"STDCPU_EBRU=%.4f\t",stdcpu_ebru);
      fprintf(fres1,"\n");

      fclose(fin);
      fclose(fres1);
      fclose(fout);
      fclose(fopt);

return 0;}

int sortarpd(){
    int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE-1;i++)
      for (j=i+1;j<MAXREP*NUMINSTANCE;j++)
        if (rel_per_dev[i]<rel_per_dev[j]){
        temp=rel_per_dev[i];
        rel_per_dev[i]=rel_per_dev[j];
        rel_per_dev[j]=temp;}
  return 0; }

int sortcpu(){
    int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE-1;i++)
      for (j=i+1;j<MAXREP*NUMINSTANCE;j++)
        if (cpu_time[i]<cpu_time[j]){
        temp=cpu_time[i];
        cpu_time[i]=cpu_time[j];
        cpu_time[j]=temp;}
    //printf("cpu=%.4f\n",cpu_time[0]);getch();
return 0; }

int sortcpu_ebru(){
    int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE-1;i++)
      for (j=i+1;j<MAXREP*NUMINSTANCE;j++)
        if (cpu_time_ebru[i]<cpu_time_ebru[j]){
        temp=cpu_time_ebru[i];
        cpu_time_ebru[i]=cpu_time_ebru[j];
        cpu_time_ebru[j]=temp;}
    //printf("cpu=%.4f\n",cpu_time[0]);getch();
return 0; }

int arpdstd(){
int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE;i++){
     tot_avg_rel_per_dev=tot_avg_rel_per_dev+rel_per_dev[i]; }
        avg_rel_per_dev=tot_avg_rel_per_dev/(MAXREP*NUMINSTANCE-1);

    for (i=0;i<MAXREP*NUMINSTANCE;i++){
      tdif1=tdif1+(rel_per_dev[i]-avg_rel_per_dev)*(rel_per_dev[i]-avg_rel_per_dev);}

      stdarpd=sqrt(tdif1/(MAXREP*NUMINSTANCE-2));

return 0; }

int cpustd(){
int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE;i++){
      tcpu_time=tcpu_time+cpu_time[i];}
      avg_cpu_time=tcpu_time/(MAXREP*NUMINSTANCE-1);

    for (i=0;i<MAXREP*NUMINSTANCE;i++){
      tdif2=tdif2+(cpu_time[i]-avg_cpu_time)*(cpu_time[i]-avg_cpu_time);}

      stdcpu=sqrt(tdif2/(MAXREP*NUMINSTANCE-2));

return 0; }

int cpustd_ebru(){
int i,j;
    float temp;
    for (i=0;i<MAXREP*NUMINSTANCE;i++){
      tcpu_time_ebru=tcpu_time_ebru+cpu_time_ebru[i];}
      avg_cpu_time_ebru=tcpu_time_ebru/(MAXREP*NUMINSTANCE-1);

    for (i=0;i<MAXREP*NUMINSTANCE;i++){
      tdif2_ebru=tdif2_ebru+(cpu_time_ebru[i]-avg_cpu_time_ebru)*(cpu_time_ebru[i]-avg_cpu_time_ebru);}

      stdcpu_ebru=sqrt(tdif2_ebru/(MAXREP*NUMINSTANCE-2));

return 0; }


int vnd1(){
int i,j,jj,k,z,m,dloop,kcount,max_method;

 // for (i=0;i<(int)popsize*plocalsearch;i++){
  for (i=0;i<1;i++){

     offspring=globalbest;

     k=rnd(0,ldimension-1);
     m=rnd(0,ldimension-1);
     interchange(&offspring1,&offspring,k,m);

     cmax_fitness=cfitness_cmax(offspring1.sequence,ldimension);
     tmax_fitness=cfitness_tmax(offspring1.sequence,ldimension);
     offspring.fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;
     for (z=0;z<ldimension;z++){
                offspring.dchrom[z]=offspring1.dchrom[z];
                offspring.vchrom[z]=offspring1.vchrom[z];
                offspring.sequence[z]=offspring1.sequence[z];}
     dloop=0;

   for (k=0;k<ldimension*(ldimension-1);k++){
     m=k+1;
     pcount=0;
     max_method=2;
     kcount=0;
     do{

              //printf("dloop=%d kcount=%d\n",dloop,kcount);getch();
              if (kcount==0) interchange(&offspring1,&offspring,k,m);
              if (kcount==1) insert(&offspring1,&offspring,k,m);
              // getsequence(&offspring1);
               //offspring1.fitness=cfitness(offspring1.sequence,ldimension);

               cmax_fitness=cfitness_cmax(offspring1.sequence,ldimension);
               tmax_fitness=cfitness_tmax(offspring1.sequence,ldimension);
               offspring1.fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;
              // printf("pop=%.2f\n",offspring1.fitness); getch();
               if (offspring1.fitness<offspring.fitness){
                   offspring.fitness=offspring1.fitness;
                   for (z=0;z<ldimension;z++){
                        offspring.dchrom[z]=offspring1.dchrom[z];
                        offspring.vchrom[z]=offspring1.vchrom[z];
                        offspring.sequence[z]=offspring1.sequence[z];}
                   kcount=0;}
               else{kcount++;}


     }while(kcount<max_method);}
      //printf("dloop=%d kcount=%d\n\n",dloop,kcount);getch();

          if (offspring.fitness<=globalbest.fitness){
            globalbest.fitness=offspring.fitness;
            repair(&offspring);
            for (z=0;z<ldimension;z++){
                globalbest.dchrom[z]=offspring.dchrom[z];
                globalbest.vchrom[z]=offspring.vchrom[z];
                globalbest.sequence[z]=offspring.sequence[z];}}}
return 0;}

int vnd2(){
int i,j,jj,k,z,m,dloop,kcount,max_method;

 // for (i=0;i<(int)popsize*plocalsearch;i++){
  for (i=0;i<1;i++){

     offspring=globalbest;

     k=rnd(0,ldimension-1);
     m=rnd(0,ldimension-1);
     insert(&offspring1,&offspring,k,m);

     cmax_fitness=cfitness_cmax(offspring1.sequence,ldimension);
     tmax_fitness=cfitness_tmax(offspring1.sequence,ldimension);
     offspring.fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;
     for (z=0;z<ldimension;z++){
                offspring.dchrom[z]=offspring1.dchrom[z];
                offspring.vchrom[z]=offspring1.vchrom[z];
                offspring.sequence[z]=offspring1.sequence[z];}
     dloop=0;

    for (k=0;k<ldimension*(ldimension-1);k++){
      m=k+1;
     pcount=0;
     max_method=2;
     kcount=0;
     do{

              //printf("dloop=%d kcount=%d\n",dloop,kcount);getch();
              if (kcount==0) insert(&offspring1,&offspring,k,m);
              if (kcount==1) interchange(&offspring1,&offspring,k,m);
              // getsequence(&offspring1);
               cmax_fitness=cfitness_cmax(offspring1.sequence,ldimension);
               tmax_fitness=cfitness_tmax(offspring1.sequence,ldimension);
               offspring1.fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;

              // printf("pop=%.2f\n",offspring1.fitness); getch();
               if (offspring1.fitness<offspring.fitness){
                   offspring.fitness=offspring1.fitness;
                   for (z=0;z<ldimension;z++){
                        offspring.dchrom[z]=offspring1.dchrom[z];
                        offspring.vchrom[z]=offspring1.vchrom[z];
                        offspring.sequence[z]=offspring1.sequence[z];}
                   kcount=0;}
               else{kcount++;}


     }while(kcount<max_method);}
      //printf("dloop=%d kcount=%d\n\n",dloop,kcount);getch();

          if (offspring.fitness<=globalbest.fitness){
            globalbest.fitness=offspring.fitness;
            repair(&offspring);
            for (z=0;z<ldimension;z++){
                globalbest.dchrom[z]=offspring.dchrom[z];
                globalbest.vchrom[z]=offspring.vchrom[z];
                globalbest.sequence[z]=offspring.sequence[z];}}}
return 0;}

int vnd3(){
int i,j,jj,k,kk,z,m,mm,dloop,kcount,max_method;

 // for (i=0;i<(int)popsize*plocalsearch;i++){
  for (i=0;i<1;i++){
     offspring=globalbest;
     interchange(&offspring1,&offspring,k,m);
     cmax_fitness=cfitness_cmax(offspring1.sequence,ldimension);
     tmax_fitness=cfitness_tmax(offspring1.sequence,ldimension);
     offspring.fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;
     for (z=0;z<ldimension;z++){
                offspring.dchrom[z]=offspring1.dchrom[z];
                offspring.vchrom[z]=offspring1.vchrom[z];
                offspring.sequence[z]=offspring1.sequence[z];}
     dloop=0;


     pcount=0;
     max_method=2;
     kcount=0;
     do{

              //printf("dloop=%d kcount=%d\n",dloop,kcount);getch();
              if (kcount==0){
               for (k=0;k<ldimension-1;k++){
                 for (m=k+1;m<ldimension;m++){
                      interchange(&offspring1,&offspring,k,m);
                      cmax_fitness=cfitness_cmax(offspring1.sequence,ldimension);
                      tmax_fitness=cfitness_tmax(offspring1.sequence,ldimension);
                      offspring1.fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;
                      //printf("k=%d kcount=%d\n",k,kcount);
                      if (offspring1.fitness<=offspring.fitness){
                          offspring.fitness=offspring1.fitness;
                          for (z=0;z<ldimension;z++){
                               offspring.dchrom[z]=offspring1.dchrom[z];
                               offspring.vchrom[z]=offspring1.vchrom[z];
                               offspring.sequence[z]=offspring1.sequence[z];}}}}}

               if (offspring.fitness<globalbest.fitness){
                   globalbest.fitness=offspring.fitness;
                   repair(&offspring);
                   for (z=0;z<ldimension;z++){
                        globalbest.dchrom[z]=offspring.dchrom[z];
                        globalbest.vchrom[z]=offspring.vchrom[z];
                        globalbest.sequence[z]=offspring.sequence[z];}
                        kcount=0;}
               else{kcount++;}

              if (kcount==1){
               for (kk=0;kk<ldimension;kk++){
                 for (mm=0;mm<ldimension;mm++){
                      insert(&offspring1,&offspring,kk,mm);
                      cmax_fitness=cfitness_cmax(offspring1.sequence,ldimension);
                      tmax_fitness=cfitness_tmax(offspring1.sequence,ldimension);
                      offspring1.fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;
                      //printf("kk=%d kcount=%d\n",kk,kcount);getch();
                      if (offspring1.fitness<=offspring.fitness){
                          offspring.fitness=offspring1.fitness;
                          for (z=0;z<ldimension;z++){
                               offspring.dchrom[z]=offspring1.dchrom[z];
                               offspring.vchrom[z]=offspring1.vchrom[z];
                               offspring.sequence[z]=offspring1.sequence[z];}}}}}

               if (offspring.fitness<globalbest.fitness){
                   globalbest.fitness=offspring.fitness;
                   repair(&offspring);
                   for (z=0;z<ldimension;z++){
                        globalbest.dchrom[z]=offspring.dchrom[z];
                        globalbest.vchrom[z]=offspring.vchrom[z];
                        globalbest.sequence[z]=offspring.sequence[z];}
                        kcount=0;}
               else{kcount++;}


     //printf("dloop=%d kcount=%d\n\n",dloop,kcount);
     }while(kcount<max_method);}



return 0;}


int interchange(individual *neighbor,individual *particle,int u,int v){
  int i,j,jcross1,jcross2;
    /* clrscr();
     printf("particle\n");
     for (j=0;j<ldimension;j++){
        printf("%.2f\t",particle->dchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",particle->vchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%d\t",particle->sequence[j]);}
        printf("\n");
        printf("\n");
getch(); */
     u=rnd(0,ldimension-1);
     do{
       v=rnd(0,ldimension-1);
       }while (u==v);
     for (i=0;i<ldimension;i++){
       neighbor->dchrom[i]=particle->dchrom[i];
       neighbor->vchrom[i]=particle->vchrom[i];
       neighbor->sequence[i]=particle->sequence[i]; }

       neighbor->sequence[u]=particle->sequence[v];
       neighbor->sequence[v]=particle->sequence[u];

       neighbor->dchrom[u]=particle->dchrom[v];
       neighbor->dchrom[v]=particle->dchrom[u];

       neighbor->vchrom[u]=particle->vchrom[v];
       neighbor->vchrom[v]=particle->vchrom[u];

  /*     printf("neighbor\n");
     for (j=0;j<ldimension;j++){
        printf("%.2f\t",neighbor->dchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",neighbor->vchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%d\t",neighbor->sequence[j]);}
        printf("\n");
        printf("\n");
getch();*/
return 0;}

int insert(individual *neighbor,individual *particle,int u,int v){
  int i,j,remove,insert;
  float temp1,temp2,temp3;
  for (i=0;i<ldimension;i++){
       neighbor->dchrom[i]=particle->dchrom[i];
       neighbor->vchrom[i]=particle->vchrom[i];
       neighbor->sequence[i]=particle->sequence[i]; }
   /*  clrscr();
     printf("particle\n");
     for (j=0;j<ldimension;j++){
        printf("%.2f\t",particle->dchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",particle->vchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%d\t",particle->sequence[j]);}
        printf("\n");
        printf("\n");
getch(); */

     remove=rnd(0,ldimension-1);
     do{
       insert=rnd(0,ldimension-1);
       }while (remove==insert);

     // printf("%d\t %d\n",remove,insert);

     temp1=particle->dchrom[remove];
     temp2=particle->vchrom[remove];
     temp3=particle->sequence[remove];
     if (remove<insert){
       for (i=remove;i<insert;i++){
          neighbor->dchrom[i]=particle->dchrom[i+1];
          neighbor->vchrom[i]=particle->vchrom[i+1];
          neighbor->sequence[i]=particle->sequence[i+1]; }

          neighbor->dchrom[insert]=temp1;
          neighbor->vchrom[insert]=temp2;
          neighbor->sequence[insert]=temp3;}
     else{
         for (i=insert+1;i<=remove;i++){
          neighbor->dchrom[i]=particle->dchrom[i-1];
          neighbor->vchrom[i]=particle->vchrom[i-1];
          neighbor->sequence[i]=particle->sequence[i-1]; }

          neighbor->dchrom[insert]=temp1;
          neighbor->vchrom[insert]=temp2;
          neighbor->sequence[insert]=temp3;}


 /*     printf("neighbor\n");
     for (j=0;j<ldimension;j++){
        printf("%.2f\t",neighbor->dchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",neighbor->vchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%d\t",neighbor->sequence[j]);}
        printf("\n");
        printf("\n");
getch();*/

return 0;}

int mutation(){
  int i,jpoint,jcross1,jcross2;
  float dvalue1,dvalue2;
  float vvalue1,vvalue2;
  for (i=0;i<(int)popsize*pmutation;i++){
        jpoint=rnd(0,popsize-1);

        jcross1=rnd(0,ldimension);
        jcross2=rnd(0,ldimension);

        dvalue1=oldpop[jpoint].dchrom[jcross1];
        dvalue2=oldpop[jpoint].dchrom[jcross2];
        oldpop[jpoint].dchrom[jcross1]=dvalue2;
        oldpop[jpoint].dchrom[jcross2]=dvalue1;

        vvalue1=oldpop[jpoint].vchrom[jcross1];
        vvalue2=oldpop[jpoint].vchrom[jcross2];
        oldpop[jpoint].vchrom[jcross1]=vvalue2;
        oldpop[jpoint].vchrom[jcross2]=vvalue1;}


return 0;}


int display(){
int i,j;
clrscr();
printf("pop\n");
    for (i=0;i<popsize;i++){
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",oldpop[i].dchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",oldpop[i].vchrom[j]);}
        printf("\n");
      for (j=0;j<ldimension;j++){
        printf("%d\t",oldpop[i].sequence[j]);}
        printf("\n");
        printf("\n");}
getch();
return 0;}

int evaluate(){
  int i,j,k;
  /*clrscr();
  for (i=0;i<popsize;i++){
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",pop[i].dchrom[j]);}
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",pop[i].vchrom[j]);}
      for (j=0;j<ldimension;j++){
        printf("%d\t",pop[i].sequence[j]);}
        printf("\n");}getch(); */
  for (i=0;i<popsize;i++){
    getsequence(&oldpop[i]);
    cmax_fitness=cfitness_cmax(oldpop[i].sequence,ldimension);
    tmax_fitness=cfitness_tmax(oldpop[i].sequence,ldimension);
    oldpop[i].fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;
    // printf("%.2f\t",oldpop[i].fitness);getch();
    localbest[i].fitness=oldpop[i].fitness;

    for (j=0;j<ldimension;j++){
        localbest[i].dchrom[j]=oldpop[i].dchrom[j];
        localbest[i].vchrom[j]=oldpop[i].vchrom[j];
        localbest[i].sequence[j]=oldpop[i].sequence[j];}}

    for (i=0;i<popsize;i++){
      if (localbest[i].fitness<=globalbest.fitness){
          globalbest.fitness=localbest[i].fitness;
            for (j=0;j<ldimension;j++){
                globalbest.dchrom[j]=localbest[i].dchrom[j];
                globalbest.vchrom[j]=localbest[i].vchrom[j];
                globalbest.sequence[j]=localbest[i].sequence[j];}}}



return 0;}

int updatevelocity(){
  int i,j,k;
  float term1,term2;
  for (i=0;i<popsize;i++){
    for (j=0;j<ldimension;j++){
      term1=2.0*urand(0.0,1.0)*(localbest[i].dchrom[j]-oldpop[i].dchrom[j]);
      term2=2.0*urand(0.0,1.0)*(globalbest.dchrom[j]-oldpop[i].dchrom[j]);
      oldpop[i].vchrom[j]=iweight*oldpop[i].vchrom[j]+term1+term2;
       if (oldpop[i].vchrom[j]>vmax) oldpop[i].vchrom[j]=vmax;
       if (oldpop[i].vchrom[j]<vmin) oldpop[i].vchrom[j]=vmin;}}
return 0;}

int updateposition(){
  int i,j,k;
  float sigma_value,position_value;
  for (i=0;i<popsize;i++){
    for (j=0;j<ldimension;j++){
      //position_value=oldpop[i].vchrom[j]+oldpop[i].dchrom[j];
      //sigma_value=1/(1+exp(-oldpop[i].vchrom[j]));
       oldpop[i].dchrom[j]=oldpop[i].vchrom[j]+oldpop[i].dchrom[j];}}

return 0;}


int evaluatelocalbest(){
  int i,j,k;
  //getsequence();
  for (i=0;i<popsize;i++){
    getsequence(&oldpop[i]);
    cmax_fitness=cfitness_cmax(oldpop[i].sequence,ldimension);
    tmax_fitness=cfitness_tmax(oldpop[i].sequence,ldimension);
    oldpop[i].fitness=lamda*cmax_fitness+(1-lamda)*tmax_fitness;

    if (oldpop[i].fitness<=localbest[i].fitness){
        localbest[i].fitness=oldpop[i].fitness;
            for (j=0;j<ldimension;j++){
              localbest[i].dchrom[j]=oldpop[i].dchrom[j];
              localbest[i].vchrom[j]=oldpop[i].vchrom[j];
              localbest[i].sequence[j]=oldpop[i].sequence[j];}}}

return 0;}

int evaluateglobalbest(){
  int i,j,k;
  for (i=0;i<popsize;i++){
    if (localbest[i].fitness<=globalbest.fitness){
        globalbest.fitness=localbest[i].fitness;
            for (j=0;j<ldimension;j++){
              globalbest.dchrom[j]=localbest[i].dchrom[j];
              globalbest.vchrom[j]=localbest[i].vchrom[j];
              globalbest.sequence[j]=localbest[i].sequence[j];}}}

return 0;}


int initialize(){
  int i,j,neh[MAXDIM];
  initpop(&oldpop[0]);

   fprintf(fout,"dataset\n");
   for (j=0;j<nmach;j++){
   for (i=0;i<njobs;i++){
        fprintf(fout,"%4d",ptime[i][j]);}
        fprintf(fout,"\n");};

  /*for (i=0;i<popsize;i++){
    for (j=0;j<ldimension;j++){
       fprintf(fout,"%0.4f %s",oldpop[i].dchrom[j],",");}
       fprintf(fout,"\n");
       fprintf(fout,"\n");}
  for (i=0;i<popsize;i++){
    for (j=0;j<ldimension;j++){
       fprintf(fout,"%0.4f %s",oldpop[i].vchrom[j],",");}
       fprintf(fout,"\n");
       fprintf(fout,"\n");}
   for (i=0;i<popsize;i++){
    for (j=0;j<ldimension;j++){
       fprintf(fout,"%d %s",oldpop[i].sequence[j],",");}
       fprintf(fout,"\n");
       fprintf(fout,"\n");}*/
return 0;}

int initpop(individual *oldpop){
  int i,j,k;
  for (i=0;i<popsize;i++){
    for (j=0;j<ldimension;j++){
    (oldpop+i)->dchrom[j]=xmin+urand(0.0,1.0)*(xmax-xmin);
    (oldpop+i)->sequence[j]=j;}}

  for (i=0;i<popsize;i++){
    for (j=0;j<ldimension;j++){
    (oldpop+i)->vchrom[j]=vmin+urand(0.0,1.0)*(vmax-vmin);}}

return 0;}




/*int randlist(int n, int list[]){
  int i,j;
  float label[MAXDIM];
  float step,u,tu;
  for(i=1;i<n;i++){
     list[i]=-1;
     label[i]=-1;}
  for(i=1;i<n;i++){
     step = 1.0 / ((float)( n-i));
     tu=0.0;
     for(j=1;j<n;j++)
       if ( label[j] ==-1 ){
         u=urand(0.0,1.0);
         tu+=step;
         if ( u <= tu){
           list[i]=j;
           label[j]=1;
           j=n;}}}
   return 0;}

float randlistf(int n, float list[]){
  int i,j;
  float label[MAXDIM];
  float step,u,tu;
  for(i=1;i<n;i++){
     list[i]=-1;
     label[i]=-1;}
  for(i=1;i<n;i++){
     step = 1.0 / ((float)( n-i));
     tu=0.0;
     for(j=1;j<n;j++)
       if ( label[j] ==-1 ){
         u=urand(0.0,1.0);
         tu+=step;
         if ( u <= tu){
           list[i]=j;
           label[j]=1;
           j=n;}}}
   return 0;}  */

float cfitness_cmax(int seq[],int lbits){
     int i,k,vcount;
     int maxctime;
     float tdist=0.0;
     comptime[seq[0]][0]=ptime[seq[0]][0];
        for (k=1;k<nmach;k++)
          comptime[seq[0]][k]=comptime[seq[0]][k-1]+ptime[seq[0]][k];

        	 for (i=1;i<njobs;i++)
            comptime[seq[i]][0]=comptime[seq[i-1]][0]+ptime[seq[i]][0];

            for (i=1;i<njobs;i++){
              for (k=1;k<nmach;k++){
                comptime[seq[i]][k]=max(comptime[seq[i]][k-1],comptime[seq[i-1]][k])+ptime[seq[i]][k];}}



 maxcomptime=comptime[seq[i-1]][nmach-1];
 //printf("\nCmax=%d\n",maxcomptime);getch();
return maxcomptime;}

float cfitness_tmax(int seq[],int lbits){
     int i,k,vcount;
     int maxctime;
     float tdist=0.0;
     comptime[seq[0]][0]=ptime[seq[0]][0];
        for (k=1;k<nmach;k++)
          comptime[seq[0]][k]=comptime[seq[0]][k-1]+ptime[seq[0]][k];

        	 for (i=1;i<njobs;i++)
            comptime[seq[i]][0]=comptime[seq[i-1]][0]+ptime[seq[i]][0];

            for (i=1;i<njobs;i++){
              for (k=1;k<nmach;k++){
                comptime[seq[i]][k]=max(comptime[seq[i]][k-1],comptime[seq[i-1]][k])+ptime[seq[i]][k];}}

       for (i=0;i<njobs;i++){
         lateness[seq[i]]=comptime[seq[i]][nmach-1]-duedate[seq[i]];}

       /*vcount=0;
       for (i=0;i<njobs;i++){
         if (lateness[seq[i]]>vcount){
             maxlateness=lateness[seq[i]];
             vcount=lateness[seq[i]];}} */
       for (i=0;i<njobs;i++){
         tardiness[seq[i]]=max(lateness[seq[i]],0);}
       vcount=0;
       for (i=0;i<njobs;i++){
         if (tardiness[seq[i]]>vcount){
             maxtardiness=tardiness[seq[i]];
             vcount=tardiness[seq[i]];}}


  //printf("\nmax lateness=%d\n",maxtardiness);getch();
return maxtardiness;}

int getsequence(individual *child){
  int i,j,k;
  int temp;
  float temp1,temp2;
  float x[MAXDIM],y[MAXDIM];
  for (j=0;j<ldimension;j++){
     child->sequence[j]=j;
     x[j]=child->dchrom[j];
     y[j]=child->vchrom[j];}
      /*for (j=0;j<ldimension;j++){
        printf("%2d",child->sequence[j]);}getch(); */

         for (j=0;j<ldimension-1;j++){
         for (k=j+1;k<ldimension;k++){
           //printf("cc=%.2f %.2f",child->dchrom[i],child->dchrom[j]);getch();
           if (child->dchrom[j]>child->dchrom[k]){
              temp2=child->dchrom[j];
              child->dchrom[j]=child->dchrom[k];
              child->dchrom[k]=temp2;

              temp1=child->vchrom[j];
              child->vchrom[j]=child->vchrom[k];
              child->vchrom[k]=temp1;

              temp=child->sequence[j];
              child->sequence[j]=child->sequence[k];
              child->sequence[k]=temp;}}}


     for (j=0;j<ldimension;j++){
       child->dchrom[j]=x[j];
       child->vchrom[j]=y[j];
       child->sequence[j]=child->sequence[j];}


     /*for (j=0;j<ldimension;j++){
        printf("%2d",child->sequence[j]);}getch(); */
 return 0;}
int repair(individual *child){
  int i,j,k;
  int temp;
  float temp1,temp2;
  float x[MAXDIM],y[MAXDIM];
  int z[MAXDIM];
  for (j=0;j<ldimension;j++){
     x[j]=child->dchrom[j];
     y[j]=child->vchrom[j];
     z[j]=child->sequence[j];}
     /*printf("before repair\n");
      for (j=0;j<ldimension;j++){
        printf("%.2f\t",child->dchrom[j]);}
        printf("\n");
        for (j=0;j<ldimension;j++){
        printf("%.2f\t",child->vchrom[j]);}
        printf("\n");
        for (j=0;j<ldimension;j++){
        printf("%d\t",child->sequence[j]);}getch();*/

         for (j=0;j<ldimension-1;j++){
         for (k=j+1;k<ldimension;k++){
           //printf("cc=%.2f %.2f",child->dchrom[i],child->dchrom[j]);getch();
           if (x[j]>x[k]){
              temp2=x[j];
              x[j]=x[k];
              x[k]=temp2;

              temp1=y[j];
              y[j]=y[k];
              y[k]=temp1;}}}

             /* temp=child->sequence[j];
              child->sequence[j]=child->sequence[k];
              child->sequence[k]=temp;}}}*/


     for (j=0;j<ldimension;j++){
       child->dchrom[z[j]]=x[j];
       child->vchrom[z[j]]=y[j];
       child->sequence[j]=child->sequence[j];}

  /*   printf("\nafter repair\n");
     for (j=0;j<ldimension;j++){
        printf("%.2f\t",child->dchrom[j]);}
        printf("\n");
        for (j=0;j<ldimension;j++){
        printf("%.2f\t",child->vchrom[j]);}
        printf("\n");
        for (j=0;j<ldimension;j++){
        printf("%d\t",child->sequence[j]);}getch(); */

 return 0;}

int rankoldpop(int ccpop){
    int i,j;
    individual temp;
    for (i=0;i<ccpop-1;i++)
      for (j=i+1;j<ccpop;j++)
        if (oldpop[i].fitness<oldpop[j].fitness){
        temp=oldpop[i];
        oldpop[i]=oldpop[j];
        oldpop[j]=temp;}
  return 0;}

/*int ranknewpop(int ccpop){
    int i,j;
    individual temp;
    for (i=0;i<ccpop-1;i++)
      for (j=i+1;j<ccpop;j++)
        if (newpop[i].fitness<newpop[j].fitness){
        temp=newpop[i];
        newpop[i]=newpop[j];
        newpop[j]=temp;}
  return 0;}
int rankpop(int ccpop){
    int i,j;
    individual temp;
    for (i=0;i<ccpop-1;i++)
      for (j=i+1;j<ccpop;j++)
        if (pop[i].fitness<pop[j].fitness){
        temp=pop[i];
        pop[i]=pop[j];
        pop[j]=temp;}
  return 0;}

/*int mutuation1(individual *child3,individual *parent3){
  int i,k,clength=0;
  int pair3[32];
  child3->chrom[0]=0;
  child3->chrom[31]=31;
  for (i=0;i<ldimension-1;i++){
    if (parent3->chrom[i]>0) clength++;}
       jcross1=rnd(1,clength-(int)clength/2);
       jcross2=rnd(clength-(int)clength/2+1,clength);
       for (i=0;i<ldimension;i++){
           child3->chrom[i]=parent3->chrom[i];}
           k=0;
           for (i=jcross2;i>=jcross1;i--){
               pair3[k]=parent3->chrom[i];k++;}
               k=0;
               for (i=jcross1;i<=jcross2;i++){
                    child3->chrom[i]=pair3[k];k++;}

  return 0;}


individual tournamentselect(int nt){
 int i,j,delpoint;
 individual tour;
 tour.fitness=0.0;
 for (i=0;i<nt;i++){
    j=rnd(0,counter-1);
    if (oldpop[j].fitness>=tour.fitness){
        tour.fitness=oldpop[j].fitness;
        tour.tdistance=oldpop[j].tdistance;
        tour=oldpop[j];
        delpoint=j;}}
        delpop(delpoint);
return tour;}

individual tourselect(int nt){
 int i,j;
 individual best1;
 best1.fitness=0.0;
 for (i=0;i<nt;i++){
    j=rnd(0,popsize-1);
    if (oldpop[j].fitness>=best1.fitness){
        best1.fitness=oldpop[j].fitness;
        best1.tdistance=oldpop[j].tdistance;
        best1=oldpop[j];}}
   return best1;}


int reorder(int newchrom[]){
   int i,j;
   int liste1[32];

      newchrom[0]=0;
      newchrom[31]=31;
      clength=0;
      for (i=0;i<ldimension-1;i++){
        if (newchrom[i]>0){
           liste1[clength]=newchrom[i];
           clength++;}}

      for (i=0;i<ldimension-1;i++){
           newchrom[i]=0;
           newchrom[i]=0;}
           for (i=0;i<clength;i++)
             newchrom[i+1]=liste1[i];
   return 0;} */



long int rnd(long int low,long int up){
    long int range,result;
    range=up-low+1;
    result=random(range);
    return (result+low);}

float rndf(float low,float up){
    float range,result;
    range=up-low+1;
    result=random(range);
    return (result+low);}

float frand(){
     return rand()/(RAND_MAX+1.0); }


float urand(float low, float upper)
{
float uu;
uu=(float)(low+(upper-low)*( (float) rand()/(float) RAND_MAX) );
if (uu==0.000 || uu==1.000) uu=urand(low,upper);

return uu;
}
